package 算法.LeetCode91.每日打卡题目;

import java.util.*;

/**
 * @author:谢君臣
 * @Date:2021/3/1817:52
 * @version:1.0
 * @function: 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
 * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
 * 说明：
 * 字母异位词指字母相同，但排列不同的字符串。
 * 不考虑答案输出的顺序。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day37 {
    public static void main(String[] args) {
        findAnagrams("cbaabacd", "abc");
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length())
            return res;
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        for (int i = 0; i < p.length(); i++) {
            c1[p.charAt(i) - 'a']++;
        }
        int j = -p.length()+1;
        for (int i = 0; i < s.length(); i++,j++) {
            c2[s.charAt(i)-'a']++;
            if (j>=0){
                if (Arrays.equals(c1,c2))
                    res.add(j);
                c2[s.charAt(j)-'a']--;
            }
        }
        return res;
    }

    public static List<Integer> findAnagrams1(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length())
            return res;
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        int i = 0;
        for (; i < p.length(); i++) {
            c1[s.charAt(i) - 'a']++;
            c2[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(c1, c2))
            res.add(0);
        for (i = p.length(); i < s.length(); i++) {
            c1[s.charAt(i - p.length()) - 'a']--;
            c1[s.charAt(i) - 'a']++;
            if (Arrays.equals(c1, c2))
                res.add(i - p.length() + 1);
        }
        return res;
    }
}
